package tree;

/**
 * 题目：递增序列求二叉搜索树
 *
 * @Author Gavin
 * @date 2022.01.05 22:19
 */
public class tree_17 {
    /**
     * 解题思路：二叉搜索树左节点都要小于根节点小于右节点，
     * 由于给的是一个递增的序列，所有可以按照中位数把数组分割为左右两部分，
     * 左边的就是left子树，右边的就是右子树
     * 然后递归
     */
    //Time:O(n) Space:O(log(n))
    public TreeNode build(int[] nums, int start, int end) {
        if (start > end) return null;
        //首先确定根节点，也就是mid部分的节点
        //(end-start)/2 +start
//        int mid=start+(end-nums.length/2);
        int mid = nums[start + (end - start) / 2];
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, start, mid - 1);
        root.right = build(nums, mid + 1, end);
        return root;
    }

    public TreeNode solution_1(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        return build(nums, 0, nums.length - 1);
    }
}
